902. Numbers At Most N Given Digit Set - LeetCode Solution


Array Math Binary Search

Python Code:

class Solution:
    def atMostNGivenDigitSet(self, D: List[str], N: int) -> int:
        S = str(N)
        K = len(S)
        dp = [0] * K + [1]

        for i in range(K-1, -1, -1):
            # Compute dp[i]

            for d in D:
                if d < S[i]:
                    dp[i] += len(D) ** (K-i-1)
                elif d == S[i]:
                    dp[i] += dp[i+1]

        return dp[0] + sum(len(D) ** i for i in range(1, K))


Comments

Submit
0 Comments
More Questions

22A - Second Order Statistics
1720B - Interesting Sum
1720A - Burenka Plays with Fractions
3A - Shortest path of the king
1720C - Corners
574A - Bear and Elections
352B - Jeff and Periods
1244A - Pens and Pencils
1670A - Prof Slim
1189A - Keanu Reeves
678A - Johny Likes Numbers
1699C - The Third Problem
1697D - Guess The String
754B - Ilya and tic-tac-toe game
760A - Petr and a calendar
1573A - Countdown
166A - Rank List
1631B - Fun with Even Subarrays
727A - Transformation from A to B
822B - Crossword solving
1623A - Robot Cleaner
884B - Japanese Crosswords Strike Back
862B - Mahmoud and Ehab and the bipartiteness
429A - Xor-tree
1675C - Detective Task
950A - Left-handers Right-handers and Ambidexters
672B - Different is Good
1C - Ancient Berland Circus
721A - One-dimensional Japanese Crossword
1715B - Beautiful Array